Search Results

1. I. Kudjoi, Applying the Gittins Index to Scheduling of a Queueing System, Master's thesis, TKK Helsinki University of Technology, 2007 (bib)

   Abstract: Multi-armed bandit is a known machine learning problem, in which there are $n$ machines, which yield a random reward once they are allocated one at a time. The question assigned to the system is, how to find an optimal allocation order for the bandits, so that the system would produce best possible reward stream. Gittins index is recognised as a powerful solution of the problem, but it is not that widely known that the index can be also used to schedule queueing systems. There exists various publications on the topic, but the common factor for most of them is that they are not too easy to follow, especially the original proof by the father of the Gittins index, J.C. Gittins, is challenging. The motivation of this thesis is therefore to study the relevant publications and to assemble a summarising work on this topic that would be easier to follow. This is achieved by providing introduction to the relevant basic theory related to the topic and to the Gittins index. Further the focus is placed on the generalisation of the index for scheduling of a one server queueing system by simplifying and picking up the most relevant parts of the proof by Gittins to this thesis. In practise the thesis shows that the Gittins index minimises the expected weighted flow-time (EWFT) of an M/G/1-queueing system, but there is no question about whether or not the index couldn't be generalised further to make also other types of schedulers more effective. However, the further generalisations is to be covered by further research.